#include<vector>
#include<string>
using namespace std;

class Solution {
private:
    struct Node {
        int index;
        vector<Node*>childs;
        Node(int index=-1):index(index),childs(26){}
    };

public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        Node* tree=new Node();
        for (int i = 0; i < smalls.size(); ++i) {
            Node* node = tree;
            auto& small = smalls[i];
            for (int j = 0; j < small.size(); ++j) {
                int index = small[j] - 'a';
                if (node->childs[index] == NULL)
                    node->childs[index] = new Node();
                node = node->childs[index];
            }
            node->index = i;
        }
        vector<vector<int>>res(smalls.size());
        for (int i = 0; i < big.size(); ++i) {
            Node* node = tree;
            for (int j = i; j < big.size(); ++j) {
                node = node->childs[big[j] - 'a'];
                if (node == NULL) break;
                if (node->index != -1)
                    res[node->index].push_back(i);
            }
        }
        return res;
    }
};